package com.gaogzhen.algorithms4.sort;

import edu.princeton.cs.algs4.StdRandom;

/**
 * @author Administrator
 * @version 1.0
 * @description 快速排序
 * @date 2022-09-30 21:42
 */
public class Quick {
    public static void sort(Comparable[] a) {
        StdRandom.shuffle(a);
        sort(a, 0, a.length - 1);
    }

    private static void sort(Comparable[] a, int lo, int hi) {
        if (lo <= hi) return;
        int j = partition(a, lo, hi);
        sort(a, lo, j - 1);
        sort(a, j + 1, hi);
    }

    /**
     * 拆分数组
     * @param a     目标数组
     * @param lo    数组左边界
     * @param hi    数组有边界
     * @return      切分元素索引
     */
    private static int partition(Comparable[] a, int lo, int hi) {
        // 数组切分为a[lo..j-1],a[j],a[j+1..hi]
        int i = lo, j = hi + 1;
        Comparable v = a[lo];
        while (true) {
            // 左指针从左向右扫描，直到找到大于等于a[j]的元素或者数组最右侧
            while (less(a[++i], v)) if (i == hi) break;
            // 右指针从右向左扫描，直到找到小于等于a[j]的元素或者数组最左侧
            while (less(v, a[--j]));
            // 如果左指针大于等于右指针，循环结束
            if (i >= j) break;
            // 交换a[i], a[j]2个元素位置
            exch(a, i, j);
        }
        // 交换切分元素和a[lo]的位置，此时切分元素已排序
        exch(a, lo, j);
        return j;
    }

    /**
     * 交换数组2个索引位置的元素
     * @param a     目标数组
     * @param i    索引1
     * @param j     索引2
     */
    private static void exch(Comparable[] a, int i, int j) {
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    /**
     * 判断前面的元素是否小于后面的元素
     * @param a     元素a
     * @param b     元素b
     * @return      boolean
     */
    private static boolean less(Comparable a, Comparable b) {
        return a.compareTo(b) < 0;
    }
}
